Embedding an Edge-colored $K(a^{(p)};\lambda,\mu )$ into a Hamiltonian Decomposition of $K(a^{(p+r)};\lambda,\mu )$

摘要

Let $K(a^{(p)};\lambda,\mu )$ be a graph with $p$ parts, each part havingsize $a$, in which the multiplicity of each pair of vertices in the same part(in different parts) is $\lambda$ ($\mu $, respectively). In this paper weconsider the following embedding problem: When can a graph decomposition of$K(a^{(p)};\lambda,\mu )$ be extended to a Hamiltonian decomposition of$K(a^{(p+r)};\lambda,\mu )$ for $r>0$? A general result is proved, which isthen used to solve the embedding problem for all $r\geq \frac{\lambda}{\mua}+\frac{p-1}{a-1}$. The problem is also solved when $r$ is as small aspossible in two different senses, namely when $r=1$ and when$r=\frac{\lambda}{\mu a}-p+1$.